package DataStructure.peixu;

public class Quick {

    public static void sort(Comparable[] a){
        int lo=0;
        int hi= a.length-1;
        sort(a,lo,hi);

    }

    private static void sort(Comparable[] a,int lo,int hi){
        //安全性校验
        if(lo>=hi){
            return;
        }
        //需要对数组中lo 到hi 的元素分组
        int partition = partition(a,lo,hi);
        //让左子树有序
        sort(a,lo,partition-1);
        //让右子数有序
        sort(a,partition+1,hi);
    }



    //进行分组，返回分界对应的索引
    public static int partition(Comparable[] a,int lo,int hi){
        //确定分界值
        Comparable key = a[lo];
        //定义两个指针，分别指向待切分数组的最小索引处和最大索引处
        int left = lo;
        int right = hi+1;
        while (true){
            //先从右往左扫描，移动right指针，找到一个比分界值小的元素
            while (less(key,a[--right])){
                if(right==lo){
                    break;
                }
            }
            //再从左往右，移动left指针，找到一个比分界值大的元素
            while (less(a[++left],key)){
                if(left==hi){
                    break;
                }
            }
            //判断left>=right,如果是则结束循环,如果不是则交换元素
            if(left>=right){
                break;
            }else {
                exch(a,left,right);
            }
        }
        //交换分界值
        exch(a,lo,right);
        return right;
    }




    private static boolean less(Comparable v,Comparable w){return v.compareTo(w)<0;}

    private static void exch(Comparable[] a,int i,int j){
        Comparable temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}
